A Gray code is an ordered collection of binary integers, all having the same number of bits, where the collection has the property that only one bit changes as the different integers are visited in the ordering associated with that collection. Although the numeric value of the bits in an entry in the collection can be construed as an arabic binary number, the ordering is generally not produced by adding unity to an entry in the collection to find its successor. In a very real sense a Gray code IS the “contrived” arrangement of a sequence of binary integers into an ordering of the particular type noted above, and there is more than one Gray code. And while programmatically executed algorithmic and logical operations can be used to generate and then operate on Gray codes, and gating implemented in hardware can ‘increment’ and ‘decrement’ Gray code counters and also convert between Gray code and true binary, such operations are generally not viewed as being arithmetic in nature.
Gray codes are useful in limiting ambiguity in encoders, in interfaces that communicate across the boundaries of mechanisms controlled by separate clock signals, and also for limiting the generation of noise or of glitches on power supplies and grounds that might be caused by a large number of logic elements changing state at one time (e.g., a transition from 001111 to 010000). It is common in high speed data communication circuitry for the Gray code in use to be implemented in hardware; e.g., counters that count using a particular Gray code and for addressing of finite state machines.
There is a particular Gray code that is often called the ‘standard’ Gray code; it is a popular instance of a class of codes that are properly called a reflected binary code. A reflected binary code is cyclic, and most have a full 2n different entries for n-many bits. (By ‘cyclic’ we mean that the ‘first’ and ‘last’ entries in the ordering are still just one bit apart, so that the ordering ‘wraps around’ to start over.) It appears that these reflected binary codes were first described by Frank Gray of Bell Telephone Laboratories in U.S. Pat. No. 2,632,058 entitled PULSE CODE COMMUNICATION, issued 17 Mar. 1953. Subsequently, a fair amount of attention has been focused on Gray codes, ‘standard’ and otherwise. See, for example: Appendix II in LOGICAL DESIGN OF DIGITAL COMPUTERS by Montgomery Phister, Jr. 8th ed. 1966, from John Wiley & Sons; §5.2 (Subsets of Sets) in Combinatorial Algorithms: Theory and Practice by Reingold, Nieverglet and Deo, 1977, from Prentice-Hall (ISBN 0-13-152447-X); and §20.2 in NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5), 1992, from Cambridge University Press. Gray codes continue to find ever wider applications in a variety of diverse fields, as even a quick perusal of the following web sites will illustrate: http://www.nist.gov/dads/HTML/graycode.html and, http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/www/Q21.htm.
Conventional techniques for discovering or generating a Gray code are limited to codes that have 2n-many entries, where n is the number of bits of each integer. This is unfortunate, as there are applications where a Gray code with a fewer number of entries will suffice. However, most of the subsets of a 2n Gray code are not cyclic, a disadvantage that may very well preclude their usefulness. A reliable method for generating cyclic Gray codes having less than 2n entries would save hardware and power consumption for those applications that do not require a full 2n entries. By less than 2n entries we mean, of course, that a full power of two is more entries within an n-bit Gray code than we actually need, and that some number of entries m, where 2(n−1)<m<2n, would do just fine. So the question is, “How can we find cyclic Gray codes of n-many bits that have m-many entries?”